'''
什么是插入排序？
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。
是稳定的排序方法。

具体做法，就是把当前元素和前面的元素依次比较，如果当前元素比前面的元素小，则交换位置。
这里假设前面的元素都是有序的，所以每次只需要比较一个元素就可以确定插入的位置。
'''

# 插入排序
def insertion_sort(arr):
    n = len(arr)
    # 遍历所有数组元素
    for i in range(1, n):
        # 当前元素
        key = arr[i]
        # 当前元素前面的所有元素
        j = i-1
        # 将当前元素插入前面元素的正确位置，这里是假设前面元素都是有序的，将当前元素和前面的元素依次比较，如果当前元素比前面的元素小，则交换位置。
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

# 示例
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print(sorted_arr)